package com.fr.lintcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.junit.Test;

public class Q872 {
    /**
     * @param pid:
     *            the process id
     * @param ppid:
     *            the parent process id
     * @param kill:
     *            a PID you want to kill
     * @return: a list of PIDs of processes that will be killed in the end
     */
    public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
        // Write your code here
        List<Integer> rs = new ArrayList<>();
        if (pid == null || pid.size() == 0 || ppid == null || ppid.size() == 0) {
            return rs;
        }
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < pid.size(); i++) {
            Integer id = pid.get(i);
            Integer idp = ppid.get(i);
            List<Integer> pp = map.get(idp);
            if (pp == null) {
                pp = new ArrayList<>();
                map.put(idp, pp);
            }
            if (id > 0) {
                pp.add(id);
            }

        }
        List<Integer> tmp = new ArrayList<>();
        tmp.add(kill);
        while (tmp.size() > 0) {
            List<Integer> tmp2 = new ArrayList<>();
            for (Integer id : tmp) {
                rs.add(id);
                List<Integer> p = map.get(id);
                if (p != null) {
                    tmp2.addAll(p);
                }
            }
            tmp = tmp2;
        }
        return rs;
    }

    @Test
    public void testA() {
        List<Integer> pid = Arrays.asList(1, 3, 10, 5);
        List<Integer> ppid = Arrays.asList(3, 0, 5, 3);
        List<Integer> rs = killProcess(pid, ppid, 5);
        System.out.print(rs);
    }

}
